package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
		Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
	
	Example:
	Given nums = [-2, 0, 3, -5, 2, -1]
	
	sumRange(0, 2) -> 1
	sumRange(2, 5) -> -1
	sumRange(0, 5) -> -3
	Note:
	You may assume that the array does not change.
	There are many calls to sumRange function.
	
题目大意
	给定一个整数数组nums，找到索引i和j（i≤j）之间的元素之和（包括）。
	
	例：
	给定nums = [-2,0,3，-5,2，-1]
	
	sumRange（0,2） - > 1
	sumRange（2，5） - > -1
	sumRange（0，5） - > -3
	注意：
	您可以假定阵列不变。
	对sumRange函数有很多调用。
	
解题思路
       当前i的sum[i] = sum[i-1]+num[i]
      i到j的元素和为 sum[j]- sum[i-1]
      
   @Type: 动态规划
 * @Date 2017-09-18 13：38
 */
public class _303_Range_Sum_Query_Immutable {
	/**
	 * sum[4]：表示num数组索引0到索引4之间所有元素值的和		  //包括0,包括4
	 */
	private int[] sum;
    public _303_Range_Sum_Query_Immutable(int[] nums) {
        if (nums==null || nums.length==0) {
        	sum = null;
        } else {
        	sum = new int[nums.length];
        	sum[0] = nums[0];
        	for (int i = 1; i < nums.length; i ++) {
        		sum[i] = sum[i-1]+nums[i];
        	}
        }
    }
    
    public int sumRange(int i, int j) {
    	if (sum == null)	return 0;
    	if (i>j || i<0 || j>=sum.length)	return 0;
    	if (i == 0)	
    		return sum[j];
    	return sum[j] - sum[i-1];
    }
    
	public static void main(String[] args) {
		_303_Range_Sum_Query_Immutable obj = new _303_Range_Sum_Query_Immutable(new int[] {3, 5, 2, 1, 6, 7});
		
	}

}
